home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 21 / AACD 21.iso / AACD / Utilities / Ghostscript / src / gxfill.c < prev    next >
Encoding:
C/C++ Source or Header  |  2001-01-01  |  51.3 KB  |  1,669 lines
  1. /* Copyright (C) 1989, 2000 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of AFPL Ghostscript.
  4.   
  5.   AFPL Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author or
  6.   distributor accepts any responsibility for the consequences of using it, or
  7.   for whether it serves any particular purpose or works at all, unless he or
  8.   she says so in writing.  Refer to the Aladdin Free Public License (the
  9.   "License") for full details.
  10.   
  11.   Every copy of AFPL Ghostscript must include a copy of the License, normally
  12.   in a plain ASCII text file named PUBLIC.  The License grants you the right
  13.   to copy, modify and redistribute AFPL Ghostscript, but only under certain
  14.   conditions described in the License.  Among other things, the License
  15.   requires that the copyright notice and this notice be preserved on all
  16.   copies.
  17. */
  18.  
  19. /*$Id: gxfill.c,v 1.5 2000/09/19 19:00:36 lpd Exp $ */
  20. /* Lower-level path filling procedures */
  21. #include "gx.h"
  22. #include "gserrors.h"
  23. #include "gsstruct.h"
  24. #include "gxfixed.h"
  25. #include "gxdevice.h"
  26. #include "gzpath.h"
  27. #include "gzcpath.h"
  28. #include "gxdcolor.h"
  29. #include "gxhttile.h"
  30. #include "gxistate.h"
  31. #include "gxpaint.h"        /* for prototypes */
  32.  
  33. /* Define which fill algorithm(s) to use. */
  34. #define FILL_SCAN_LINES
  35. #define FILL_CURVES
  36. #define FILL_TRAPEZOIDS
  37.  
  38. /* Statistics */
  39. #ifdef DEBUG
  40. struct stats_fill_s {
  41.     long
  42.     fill, fill_alloc, y_up, y_down, horiz, x_step, slow_x, iter, find_y,
  43.     band, band_step, band_fill, afill, slant, slant_shallow, sfill,
  44.     mq_cross, cross_slow, cross_low, order, slow_order;
  45. } stats_fill;
  46.  
  47. #  define INCR(x) (++(stats_fill.x))
  48. #  define INCR_EXPR(x) INCR(x)
  49. #  define INCR_BY(x,n) (stats_fill.x += (n))
  50. #else
  51. #  define INCR(x) DO_NOTHING
  52. #  define INCR_EXPR(x) discard(0)
  53. #  define INCR_BY(x,n) DO_NOTHING
  54. #endif
  55.  
  56. /* Define the structure for keeping track of active lines. */
  57. typedef struct active_line_s active_line;
  58. struct active_line_s {
  59.     gs_fixed_point start;    /* x,y where line starts */
  60.     gs_fixed_point end;        /* x,y where line ends */
  61.     gs_fixed_point diff;    /* end - start */
  62. #define al_dx(alp) ((alp)->diff.x)
  63. #define al_dy(alp) ((alp)->diff.y)
  64.     fixed y_fast_max;        /* can do x_at_y in fixed point */
  65.                 /* if y <= y_fast_max */
  66.     fixed num_adjust;        /* 0 if diff.x >= 0, -diff.y + epsilon if */
  67.                 /* diff.x < 0 and division truncates */
  68. #if ARCH_DIV_NEG_POS_TRUNCATES
  69.     /* neg/pos truncates, we must bias the numberator. */
  70. #  define SET_NUM_ADJUST(alp) \
  71.     (alp)->num_adjust =\
  72.       ((alp)->diff.x >= 0 ? 0 : -(alp)->diff.y + fixed_epsilon)
  73. #  define ADD_NUM_ADJUST(num, alp) ((num) + (alp)->num_adjust)
  74. #  define MAX_MINUS_NUM_ADJUST(alp) ADD_NUM_ADJUST(max_fixed, alp)
  75. #else
  76.     /* neg/pos takes the floor, no special action is needed. */
  77. #  define SET_NUM_ADJUST(alp) DO_NOTHING
  78. #  define ADD_NUM_ADJUST(num, alp) (num)
  79. #  define MAX_MINUS_NUM_ADJUST(alp) max_fixed
  80. #endif
  81. #define set_al_points(alp, startp, endp)\
  82.   BEGIN\
  83.     (alp)->diff.y = (endp).y - (startp).y;\
  84.     (alp)->diff.x = (endp).x - (startp).x;\
  85.     SET_NUM_ADJUST(alp);\
  86.     (alp)->y_fast_max = MAX_MINUS_NUM_ADJUST(alp) /\
  87.       (((alp)->diff.x >= 0 ? (alp)->diff.x : -(alp)->diff.x) | 1) +\
  88.       (startp).y;\
  89.     (alp)->start = startp, (alp)->end = endp;\
  90.   END
  91.     /*
  92.      * We know that alp->start.y <= yv <= alp->end.y, because the fill loop
  93.      * guarantees that the only lines being considered are those with this
  94.      * property.
  95.      */
  96. #define al_x_at_y(alp, yv)\
  97.   ((yv) == (alp)->end.y ? (alp)->end.x :\
  98.    ((yv) <= (alp)->y_fast_max ?\
  99.     ADD_NUM_ADJUST(((yv) - (alp)->start.y) * al_dx(alp), alp) / al_dy(alp) :\
  100.     (INCR_EXPR(slow_x),\
  101.      fixed_mult_quo(al_dx(alp), (yv) - (alp)->start.y, al_dy(alp)))) +\
  102.    (alp)->start.x)
  103.     fixed x_current;        /* current x position */
  104.     fixed x_next;        /* x position at end of band */
  105.     const segment *pseg;    /* endpoint of this line */
  106.     int direction;        /* direction of line segment */
  107. #define dir_up 1
  108. #define dir_horizontal 0    /* (these are handled specially) */
  109. #define dir_down (-1)
  110.     int curve_k;        /* # of subdivisions for curves, */
  111.     /* -1 for lines */
  112.     curve_cursor cursor;    /* cursor for curves, */
  113.     /* unused for lines */
  114. /* "Pending" lines (not reached in the Y ordering yet) use next and prev */
  115. /* to order lines by increasing starting Y.  "Active" lines (being scanned) */
  116. /* use next and prev to order lines by increasing current X, or if the */
  117. /* current Xs are equal, by increasing final X. */
  118.     active_line *prev, *next;
  119. /* Link together active_lines allocated individually */
  120.     active_line *alloc_next;
  121. };
  122.  
  123. /*
  124.  * Define the ordering criterion for active lines that overlap in Y.
  125.  * Return -1, 0, or 1 if lp1 precedes, coincides with, or follows lp2.
  126.  *
  127.  * The lines' x_current values are correct for some Y value that crosses
  128.  * both of them and that is not both the start of one and the end of the
  129.  * other.  (Neither line is horizontal.)  We want the ordering at this
  130.  * Y value, or, of the x_current values are equal, greater Y values
  131.  * (if any: this Y value might be the end of both lines).
  132.  */
  133. private int
  134. x_order(const active_line *lp1, const active_line *lp2)
  135. {
  136.     bool s1;
  137.  
  138.     INCR(order);
  139.     if (lp1->x_current < lp2->x_current)
  140.     return -1;
  141.     else if (lp1->x_current > lp2->x_current)
  142.     return 1;
  143.     /*
  144.      * We need to compare the slopes of the lines.  Start by
  145.      * checking one fast case, where the slopes have opposite signs.
  146.      */
  147.     if ((s1 = lp1->start.x < lp1->end.x) != (lp2->start.x < lp2->end.x))
  148.     return (s1 ? 1 : -1);
  149.     /*
  150.      * We really do have to compare the slopes.  Fortunately, this isn't
  151.      * needed very often.  We want the sign of the comparison
  152.      * dx1/dy1 - dx2/dy2, or (since we know dy1 and dy2 are positive)
  153.      * dx1 * dy2 - dx2 * dy1.  However, we can't simply do this using
  154.      * doubles, since we need complete accuracy and doubles don't have
  155.      * enough fraction bits.
  156.      *
  157.      * ****** FOR THE MOMENT, PUNT. ******
  158.      */
  159.     INCR(slow_order);
  160.     {
  161.     double diff = ((double)(lp1->end.x - lp1->start.x) *
  162.                (lp2->end.y - lp2->start.y)) -
  163.         ((double)(lp2->end.x - lp2->start.x) *
  164.          (lp1->end.y - lp1->start.y));
  165.  
  166.     return
  167.         (diff < 0 ? -1 : diff > 0 ? 1 : 0);
  168.     }
  169. }
  170.  
  171. /*
  172.  * The active_line structure isn't really simple, but since its instances
  173.  * only exist temporarily during a fill operation, we don't have to
  174.  * worry about a garbage collection occurring.
  175.  */
  176. gs_private_st_simple(st_active_line, active_line, "active_line");
  177.  
  178. #ifdef DEBUG
  179. /* Internal procedures for printing and checking active lines. */
  180. private void
  181. print_active_line(const char *label, const active_line * alp)
  182. {
  183.     dlprintf5("[f]%s 0x%lx(%d): x_current=%f x_next=%f\n",
  184.           label, (ulong) alp, alp->direction,
  185.           fixed2float(alp->x_current), fixed2float(alp->x_next));
  186.     dlprintf5("    start=(%f,%f) pt_end=0x%lx(%f,%f)\n",
  187.           fixed2float(alp->start.x), fixed2float(alp->start.y),
  188.           (ulong) alp->pseg,
  189.           fixed2float(alp->end.x), fixed2float(alp->end.y));
  190.     dlprintf2("    prev=0x%lx next=0x%lx\n",
  191.           (ulong) alp->prev, (ulong) alp->next);
  192. }
  193. private void
  194. print_line_list(const active_line * flp)
  195. {
  196.     const active_line *lp;
  197.  
  198.     for (lp = flp; lp != 0; lp = lp->next) {
  199.     fixed xc = lp->x_current, xn = lp->x_next;
  200.  
  201.     dlprintf3("[f]0x%lx(%d): x_current/next=%g",
  202.           (ulong) lp, lp->direction,
  203.           fixed2float(xc));
  204.     if (xn != xc)
  205.         dprintf1("/%g", fixed2float(xn));
  206.     dputc('\n');
  207.     }
  208. }
  209. #define print_al(label,alp)\
  210.   if ( gs_debug_c('F') ) print_active_line(label, alp)
  211. private int
  212. check_line_list(const active_line * flp)
  213. {
  214.     const active_line *alp;
  215.  
  216.     if (flp != 0)
  217.     for (alp = flp->prev->next; alp != 0; alp = alp->next)
  218.         if (alp->next != 0 && alp->next->x_current < alp->x_current) {
  219.         lprintf("[f]Lines out of order!\n");
  220.         print_active_line("   1:", alp);
  221.         print_active_line("   2:", alp->next);
  222.         return_error(gs_error_Fatal);
  223.         }
  224.     return 0;
  225. }
  226. #else
  227. #define print_al(label,alp) DO_NOTHING
  228. #endif
  229.  
  230. /* Line list structure */
  231. struct line_list_s {
  232.     gs_memory_t *memory;
  233.     active_line *active_area;    /* allocated active_line list */
  234.     active_line *next_active;    /* next allocation slot */
  235.     active_line *limit;        /* limit of local allocation */
  236.     int close_count;        /* # of added closing lines */
  237.     active_line *y_list;    /* Y-sorted list of pending lines */
  238.     active_line *y_line;    /* most recently inserted line */
  239.     active_line x_head;        /* X-sorted list of active lines */
  240. #define x_list x_head.next
  241.     /* Put the arrays last so the scalars will have */
  242.     /* small displacements. */
  243.     /* Allocate a few active_lines locally */
  244.     /* to avoid round trips through the allocator. */
  245. #if arch_small_memory
  246. #  define max_local_active 5    /* don't overburden the stack */
  247. #else
  248. #  define max_local_active 20
  249. #endif
  250.     active_line local_active[max_local_active];
  251. };
  252. typedef struct line_list_s line_list;
  253. typedef line_list *ll_ptr;
  254.  
  255. /* Forward declarations */
  256. private void init_line_list(P2(ll_ptr, gs_memory_t *));
  257. private void unclose_path(P2(gx_path *, int));
  258. private void free_line_list(P1(ll_ptr));
  259. private int add_y_list(P5(gx_path *, ll_ptr, fixed, fixed,
  260.               const gs_fixed_rect *));
  261. private int add_y_line(P4(const segment *, const segment *, int, ll_ptr));
  262. private void insert_x_new(P2(active_line *, ll_ptr));
  263. private bool end_x_line(P1(active_line *));
  264.  
  265. #define fill_loop_proc(proc)\
  266. int proc(P11(ll_ptr, gx_device *,\
  267.   const gx_fill_params *, const gx_device_color *, gs_logical_operation_t,\
  268.   const gs_fixed_rect *, fixed, fixed, fixed, fixed, fixed))
  269. private fill_loop_proc(fill_loop_by_scan_lines);
  270. private fill_loop_proc(fill_loop_by_trapezoids);
  271.  
  272. /*
  273.  * This is the general path filling algorithm.
  274.  * It uses the center-of-pixel rule for filling.
  275.  * We can implement Microsoft's upper-left-corner-of-pixel rule
  276.  * by subtracting (0.5, 0.5) from all the coordinates in the path.
  277.  *
  278.  * The adjust parameters are a hack for keeping regions
  279.  * from coming out too faint: they specify an amount by which to expand
  280.  * the sides of every filled region.
  281.  * Setting adjust = fixed_half is supposed to produce the effect of Adobe's
  282.  * any-part-of-pixel rule, but it doesn't quite, because of the
  283.  * closed/open interval rule for regions.  We detect this as a special case
  284.  * and do the slightly ugly things necessary to make it work.
  285.  */
  286.  
  287. /*
  288.  * Tweak the fill adjustment if necessary so that (nearly) empty
  289.  * rectangles are guaranteed to produce some output.  This is a hack
  290.  * to work around a bug in the Microsoft Windows PostScript driver,
  291.  * which draws thin lines by filling zero-width rectangles, and in
  292.  * some other drivers that try to fill epsilon-width rectangles.
  293.  */
  294. void
  295. gx_adjust_if_empty(const gs_fixed_rect * pbox, gs_fixed_point * adjust)
  296. {
  297.     /*
  298.      * For extremely large coordinates, the obvious subtractions could
  299.      * overflow.  We can work around this easily by noting that since
  300.      * we know q.{x,y} >= p.{x,y}, the subtraction overflows iff the
  301.      * result is negative.
  302.      */
  303.     const fixed
  304.           dx = pbox->q.x - pbox->p.x, dy = pbox->q.y - pbox->p.y;
  305.  
  306.     if (dx < fixed_half && dx > 0 && (dy >= int2fixed(2) || dy < 0)) {
  307.     adjust->x = arith_rshift_1(fixed_1 + fixed_epsilon - dx);
  308.     if_debug1('f', "[f]thin adjust_x=%g\n",
  309.           fixed2float(adjust->x));
  310.     } else if (dy < fixed_half && dy > 0 && (dx >= int2fixed(2) || dx < 0)) {
  311.     adjust->y = arith_rshift_1(fixed_1 + fixed_epsilon - dy);
  312.     if_debug1('f', "[f]thin adjust_y=%g\n",
  313.           fixed2float(adjust->y));
  314.     }
  315. }
  316.  
  317. /*
  318.  * Fill a path.  This is the default implementation of the driver
  319.  * fill_path procedure.
  320.  */
  321. int
  322. gx_default_fill_path(gx_device * pdev, const gs_imager_state * pis,
  323.              gx_path * ppath, const gx_fill_params * params,
  324.          const gx_device_color * pdevc, const gx_clip_path * pcpath)
  325. {
  326.     gs_fixed_point adjust;
  327.  
  328. #define adjust_x adjust.x
  329. #define adjust_y adjust.y
  330.     gs_logical_operation_t lop = pis->log_op;
  331.     gs_fixed_rect ibox, bbox;
  332.     gx_device_clip cdev;
  333.     gx_device *dev = pdev;
  334.     gx_device *save_dev = dev;
  335.     gx_path ffpath;
  336.     gx_path *pfpath;
  337.     int code;
  338.     fixed adjust_left, adjust_right, adjust_below, adjust_above;
  339.     int max_fill_band = dev->max_fill_band;
  340.  
  341. #define no_band_mask ((fixed)(-1) << (sizeof(fixed) * 8 - 1))
  342.     bool fill_by_trapezoids;
  343.     line_list lst;
  344.  
  345.     adjust = params->adjust;
  346.     /*
  347.      * Compute the bounding box before we flatten the path.
  348.      * This can save a lot of time if the path has curves.
  349.      * If the path is neither fully within nor fully outside
  350.      * the quick-check boxes, we could recompute the bounding box
  351.      * and make the checks again after flattening the path,
  352.      * but right now we don't bother.
  353.      */
  354.     gx_path_bbox(ppath, &ibox);
  355.     if (params->fill_zero_width)
  356.     gx_adjust_if_empty(&ibox, &adjust);
  357.     /* Check the bounding boxes. */
  358.     if_debug6('f', "[f]adjust=%g,%g bbox=(%g,%g),(%g,%g)\n",
  359.           fixed2float(adjust_x), fixed2float(adjust_y),
  360.           fixed2float(ibox.p.x), fixed2float(ibox.p.y),
  361.           fixed2float(ibox.q.x), fixed2float(ibox.q.y));
  362.     if (pcpath)
  363.     gx_cpath_inner_box(pcpath, &bbox);
  364.     else
  365.     (*dev_proc(dev, get_clipping_box)) (dev, &bbox);
  366.     if (!rect_within(ibox, bbox)) {    /*
  367.                      * Intersect the path box and the clip bounding box.
  368.                      * If the intersection is empty, this fill is a no-op.
  369.                      */
  370.     if (pcpath)
  371.         gx_cpath_outer_box(pcpath, &bbox);
  372.     if_debug4('f', "   outer_box=(%g,%g),(%g,%g)\n",
  373.           fixed2float(bbox.p.x), fixed2float(bbox.p.y),
  374.           fixed2float(bbox.q.x), fixed2float(bbox.q.y));
  375.     rect_intersect(ibox, bbox);
  376.     if (ibox.p.x - adjust_x >= ibox.q.x + adjust_x ||
  377.         ibox.p.y - adjust_y >= ibox.q.y + adjust_y
  378.         ) {            /* Intersection of boxes is empty! */
  379.         return 0;
  380.     }
  381. #undef adjust_x
  382. #undef adjust_y
  383.     /*
  384.      * The path is neither entirely inside the inner clip box
  385.      * nor entirely outside the outer clip box.
  386.      * If we had to flatten the path, this is where we would
  387.      * recompute its bbox and make the tests again,
  388.      * but we don't bother right now.
  389.      *
  390.      * If there is a clipping path, set up a clipping device.
  391.      */
  392.     if (pcpath) {
  393.         dev = (gx_device *) & cdev;
  394.         gx_make_clip_device(&cdev, gx_cpath_list(pcpath));
  395.         cdev.target = save_dev;
  396.         cdev.max_fill_band = save_dev->max_fill_band;
  397.         (*dev_proc(dev, open_device)) (dev);
  398.     }
  399.     }
  400.     /*
  401.      * Compute the proper adjustment values.
  402.      * To get the effect of the any-part-of-pixel rule,
  403.      * we may have to tweak them slightly.
  404.      * NOTE: We changed the adjust_right/above value from 0.5+epsilon
  405.      * to 0.5 in release 5.01; even though this does the right thing
  406.      * in every case we could imagine, we aren't confident that it's
  407.      * correct.  (The old values were definitely incorrect, since they
  408.      * caused 1-pixel-wide/high objects to color 2 pixels even if
  409.      * they fell exactly on pixel boundaries.)
  410.      */
  411.     if (adjust.x == fixed_half)
  412.     adjust_left = fixed_half - fixed_epsilon,
  413.         adjust_right = fixed_half /* + fixed_epsilon */ ;    /* see above */
  414.     else
  415.     adjust_left = adjust_right = adjust.x;
  416.     if (adjust.y == fixed_half)
  417.     adjust_below = fixed_half - fixed_epsilon,
  418.         adjust_above = fixed_half /* + fixed_epsilon */ ;    /* see above */
  419.     else
  420.     adjust_below = adjust_above = adjust.y;
  421.     /* Initialize the active line list. */
  422.     init_line_list(&lst, ppath->memory);
  423.     /*
  424.      * We have a choice of two different filling algorithms:
  425.      * scan-line-based and trapezoid-based.  They compare as follows:
  426.      *
  427.      *      Scan    Trap
  428.      *      ----    ----
  429.      *       no     +yes    perfectly accurate Y adjustment
  430.      *       skip   +draw   0-height horizontal lines
  431.      *       slow   +fast   rectangles
  432.      *      +fast    slow   curves
  433.      *      +yes     no     write pixels at most once when adjust != 0
  434.      *
  435.      * Normally we use the scan line algorithm for characters, where
  436.      * curve speed is important and no Y adjustment is involved, and for
  437.      * non-idempotent RasterOps, where double pixel writing must be
  438.      * avoided, and the trapezoid algorithm otherwise.  However, we
  439.      * always use the trapezoid algorithm for rectangles.
  440.      */
  441. #define double_write_ok lop_is_idempotent(lop)
  442. #ifdef FILL_SCAN_LINES
  443. #  ifdef FILL_TRAPEZOIDS
  444.     fill_by_trapezoids =
  445.     ((adjust_below | adjust_above) != 0 || !gx_path_has_curves(ppath) ||
  446.      params->flatness >= 1.0);
  447. #  else
  448.     fill_by_trapezoids = false;
  449. #  endif
  450. #else
  451.     fill_by_trapezoids = true;
  452. #endif
  453.     if (fill_by_trapezoids && !double_write_ok) {
  454.     /* Avoid filling rectangles by scan line. */
  455.     gs_fixed_rect rbox;
  456.  
  457.     if (gx_path_is_rectangular(ppath, &rbox)) {
  458.         int x0 = fixed2int_pixround(rbox.p.x - adjust_left);
  459.         int y0 = fixed2int_pixround(rbox.p.y - adjust_below);
  460.         int x1 = fixed2int_pixround(rbox.q.x + adjust_right);
  461.         int y1 = fixed2int_pixround(rbox.q.y + adjust_above);
  462.  
  463.         return gx_fill_rectangle_device_rop(x0, y0, x1 - x0, y1 - y0,
  464.                         pdevc, dev, lop);
  465.     }
  466.     fill_by_trapezoids = false; /* avoid double write */
  467.     }
  468. #undef double_write_ok
  469.     /*
  470.      * Pre-process curves.  When filling by trapezoids, we need to
  471.      * flatten the path completely; when filling by scan lines, we only
  472.      * need to monotonize it, unless FILL_CURVES is undefined.
  473.      */
  474.     gx_path_init_local(&ffpath, ppath->memory);
  475.     if (!gx_path_has_curves(ppath))    /* don't need to flatten */
  476.     pfpath = ppath;
  477.     else
  478. #ifdef FILL_CURVES
  479.     if (fill_by_trapezoids) {
  480.     gx_path_init_local(&ffpath, ppath->memory);
  481.     code = gx_path_add_flattened_accurate(ppath, &ffpath,
  482.                           params->flatness,
  483.                           pis->accurate_curves);
  484.     if (code < 0)
  485.         return code;
  486.     pfpath = &ffpath;
  487.     } else if (gx_path_is_monotonic(ppath))
  488.     pfpath = ppath;
  489.     else {
  490.     gx_path_init_local(&ffpath, ppath->memory);
  491.     code = gx_path_add_monotonized(ppath, &ffpath);
  492.     if (code < 0)
  493.         return code;
  494.     pfpath = &ffpath;
  495.     }
  496. #else
  497.     {
  498.     gx_path_init_local(&ffpath, ppath->memory);
  499.     code = gx_path_add_flattened_accurate(ppath, &ffpath,
  500.                           params->flatness,
  501.                           pis->accurate_curves);
  502.     if (code < 0)
  503.         return code;
  504.     pfpath = &ffpath;
  505.     }
  506. #endif
  507.     if ((code = add_y_list(pfpath, &lst, adjust_below, adjust_above, &ibox)) < 0)
  508.     goto nope;
  509.     {
  510.     fill_loop_proc((*fill_loop));
  511.  
  512.     /* Some short-sighted compilers won't allow a conditional here.... */
  513.     if (fill_by_trapezoids)
  514.         fill_loop = fill_loop_by_trapezoids;
  515.     else
  516.         fill_loop = fill_loop_by_scan_lines;
  517.     code = (*fill_loop)
  518.         (&lst, dev, params, pdevc, lop, &ibox,
  519.          adjust_left, adjust_right, adjust_below, adjust_above,
  520.        (max_fill_band == 0 ? no_band_mask : int2fixed(-max_fill_band)));
  521.     }
  522.   nope:if (lst.close_count != 0)
  523.     unclose_path(pfpath, lst.close_count);
  524.     free_line_list(&lst);
  525.     if (pfpath != ppath)    /* had to flatten */
  526.     gx_path_free(pfpath, "gx_default_fill_path(flattened path)");
  527. #ifdef DEBUG
  528.     if (gs_debug_c('f')) {
  529.     dlputs("[f]  # alloc    up  down horiz step slowx  iter  find  band bstep bfill\n");
  530.     dlprintf5(" %5ld %5ld %5ld %5ld %5ld",
  531.           stats_fill.fill, stats_fill.fill_alloc,
  532.           stats_fill.y_up, stats_fill.y_down,
  533.           stats_fill.horiz);
  534.     dlprintf4(" %5ld %5ld %5ld %5ld",
  535.           stats_fill.x_step, stats_fill.slow_x,
  536.           stats_fill.iter, stats_fill.find_y);
  537.     dlprintf3(" %5ld %5ld %5ld\n",
  538.           stats_fill.band, stats_fill.band_step,
  539.           stats_fill.band_fill);
  540.     dlputs("[f]    afill slant shall sfill mqcrs order slowo\n");
  541.     dlprintf7("       %5ld %5ld %5ld %5ld %5ld %5ld %5ld\n",
  542.           stats_fill.afill, stats_fill.slant,
  543.           stats_fill.slant_shallow, stats_fill.sfill,
  544.           stats_fill.mq_cross, stats_fill.order,
  545.           stats_fill.slow_order);
  546.     }
  547. #endif
  548.     return code;
  549. }
  550.  
  551. /* Initialize the line list for a path. */
  552. private void
  553. init_line_list(ll_ptr ll, gs_memory_t * mem)
  554. {
  555.     ll->memory = mem;
  556.     ll->active_area = 0;
  557.     ll->next_active = ll->local_active;
  558.     ll->limit = ll->next_active + max_local_active;
  559.     ll->close_count = 0;
  560.     ll->y_list = 0;
  561.     ll->y_line = 0;
  562.     INCR(fill);
  563. }
  564.  
  565. /* Unlink any line_close segments added temporarily. */
  566. private void
  567. unclose_path(gx_path * ppath, int count)
  568. {
  569.     subpath *psub;
  570.  
  571.     for (psub = ppath->first_subpath; count != 0;
  572.      psub = (subpath *) psub->last->next
  573.     )
  574.     if (psub->last == (segment *) & psub->closer) {
  575.         segment *prev = psub->closer.prev, *next = psub->closer.next;
  576.  
  577.         prev->next = next;
  578.         if (next)
  579.         next->prev = prev;
  580.         psub->last = prev;
  581.         count--;
  582.     }
  583. }
  584.  
  585. /* Free the line list. */
  586. private void
  587. free_line_list(ll_ptr ll)
  588. {
  589.     gs_memory_t *mem = ll->memory;
  590.     active_line *alp;
  591.  
  592.     /* Free any individually allocated active_lines. */
  593.     while ((alp = ll->active_area) != 0) {
  594.     active_line *next = alp->alloc_next;
  595.  
  596.     gs_free_object(mem, alp, "active line");
  597.     ll->active_area = next;
  598.     }
  599. }
  600.  
  601. /*
  602.  * Construct a Y-sorted list of segments for rasterizing a path.  We assume
  603.  * the path is non-empty.  Only include non-horizontal lines or (monotonic)
  604.  * curve segments where one endpoint is locally Y-minimal, and horizontal
  605.  * lines that might color some additional pixels.
  606.  */
  607. private int
  608. add_y_list(gx_path * ppath, ll_ptr ll, fixed adjust_below, fixed adjust_above,
  609.        const gs_fixed_rect * pbox)
  610. {
  611.     register segment *pseg = (segment *) ppath->first_subpath;
  612.     int close_count = 0;
  613.  
  614.     /* fixed xmin = pbox->p.x; *//* not currently used */
  615.     fixed ymin = pbox->p.y;
  616.  
  617.     /* fixed xmax = pbox->q.x; *//* not currently used */
  618.     fixed ymax = pbox->q.y;
  619.     int code;
  620.  
  621.     while (pseg) {        /* We know that pseg points to a subpath head (s_start). */
  622.     subpath *psub = (subpath *) pseg;
  623.     segment *plast = psub->last;
  624.     int dir = 2;        /* hack to skip first segment */
  625.     int first_dir, prev_dir;
  626.     segment *prev;
  627.  
  628.     if (plast->type != s_line_close) {    /* Create a fake s_line_close */
  629.         line_close_segment *lp = &psub->closer;
  630.         segment *next = plast->next;
  631.  
  632.         lp->next = next;
  633.         lp->prev = plast;
  634.         plast->next = (segment *) lp;
  635.         if (next)
  636.         next->prev = (segment *) lp;
  637.         lp->type = s_line_close;
  638.         lp->pt = psub->pt;
  639.         lp->sub = psub;
  640.         psub->last = plast = (segment *) lp;
  641.         ll->close_count++;
  642.     }
  643.     while ((prev_dir = dir, prev = pseg,
  644.         (pseg = pseg->next) != 0 && pseg->type != s_start)
  645.         ) {            /*
  646.                  * This element is either a line or a monotonic
  647.                  * curve segment.
  648.                  */
  649.         fixed iy = pseg->pt.y;
  650.         fixed py = prev->pt.y;
  651.  
  652.         /*
  653.          * Segments falling entirely outside the ibox in Y
  654.          * are treated as though they were horizontal, *
  655.          * i.e., they are never put on the list.
  656.          */
  657. #define compute_dir(xo, xe, yo, ye)\
  658.   (ye > yo ? (ye <= ymin || yo >= ymax ? 0 : dir_up) :\
  659.    ye < yo ? (yo <= ymin || ye >= ymax ? 0 : dir_down) :\
  660.    2)
  661. #define add_dir_lines(prev2, prev, this, pdir, dir)\
  662.   if ( pdir )\
  663.    { if ( (code = add_y_line(prev2, prev, pdir, ll)) < 0 ) return code; }\
  664.   if ( dir )\
  665.    { if ( (code = add_y_line(prev, this, dir, ll)) < 0 ) return code; }
  666.         dir = compute_dir(prev->pt.x, pseg->pt.x, py, iy);
  667.         if (dir == 2) {    /* Put horizontal lines on the list */
  668.         /* if they would color any pixels. */
  669.         if (fixed2int_pixround(iy - adjust_below) <
  670.             fixed2int_pixround(iy + adjust_above)
  671.             ) {
  672.             INCR(horiz);
  673.             if ((code = add_y_line(prev, pseg,
  674.                        dir_horizontal, ll)) < 0
  675.             )
  676.             return code;
  677.         }
  678.         dir = 0;
  679.         }
  680.         if (dir > prev_dir) {
  681.         add_dir_lines(prev->prev, prev, pseg, prev_dir, dir);
  682.         } else if (prev_dir == 2)    /* first segment */
  683.         first_dir = dir;
  684.         if (pseg == plast) {
  685.         /*
  686.          * We skipped the first segment of the subpath, so the last
  687.          * segment must receive special consideration.  Note that we
  688.          * have `closed' all subpaths.
  689.          */
  690.         if (first_dir > dir) {
  691.             add_dir_lines(prev, pseg, psub->next,
  692.                   dir, first_dir);
  693.         }
  694.         }
  695.     }
  696. #undef compute_dir
  697. #undef add_dir_lines
  698.     }
  699.     return close_count;
  700. }
  701. /*
  702.  * Internal routine to test a segment and add it to the pending list if
  703.  * appropriate.
  704.  */
  705. private int
  706. add_y_line(const segment * prev_lp, const segment * lp, int dir, ll_ptr ll)
  707. {
  708.     gs_fixed_point this, prev;
  709.     register active_line *alp = ll->next_active;
  710.     fixed y_start;
  711.  
  712.     if (alp == ll->limit) {    /* Allocate separately */
  713.     alp = gs_alloc_struct(ll->memory, active_line,
  714.                   &st_active_line, "active line");
  715.     if (alp == 0)
  716.         return_error(gs_error_VMerror);
  717.     alp->alloc_next = ll->active_area;
  718.     ll->active_area = alp;
  719.     INCR(fill_alloc);
  720.     } else
  721.     ll->next_active++;
  722.     this.x = lp->pt.x;
  723.     this.y = lp->pt.y;
  724.     prev.x = prev_lp->pt.x;
  725.     prev.y = prev_lp->pt.y;
  726.     switch ((alp->direction = dir)) {
  727.     case dir_up:
  728.         y_start = prev.y;
  729.         set_al_points(alp, prev, this);
  730.         alp->pseg = lp;
  731.         break;
  732.     case dir_down:
  733.         y_start = this.y;
  734.         set_al_points(alp, this, prev);
  735.         alp->pseg = prev_lp;
  736.         break;
  737.     case dir_horizontal:
  738.         y_start = this.y;    /* = prev.y */
  739.         alp->start = prev;
  740.         alp->end = this;
  741.         /* Don't need to set dx or y_fast_max */
  742.         alp->pseg = prev_lp;    /* may not need this either */
  743.         break;
  744.     default:        /* can't happen */
  745.         return_error(gs_error_unregistered);
  746.     }
  747.     /* Insert the new line in the Y ordering */
  748.     {
  749.     register active_line *yp = ll->y_line;
  750.     register active_line *nyp;
  751.  
  752.     if (yp == 0) {
  753.         alp->next = alp->prev = 0;
  754.         ll->y_list = alp;
  755.     } else if (y_start >= yp->start.y) {    /* Insert the new line after y_line */
  756.         while (INCR_EXPR(y_up),
  757.            ((nyp = yp->next) != NULL &&
  758.             y_start > nyp->start.y)
  759.         )
  760.         yp = nyp;
  761.         alp->next = nyp;
  762.         alp->prev = yp;
  763.         yp->next = alp;
  764.         if (nyp)
  765.         nyp->prev = alp;
  766.     } else {        /* Insert the new line before y_line */
  767.         while (INCR_EXPR(y_down),
  768.            ((nyp = yp->prev) != NULL &&
  769.             y_start < nyp->start.y)
  770.         )
  771.         yp = nyp;
  772.         alp->prev = nyp;
  773.         alp->next = yp;
  774.         yp->prev = alp;
  775.         if (nyp)
  776.         nyp->next = alp;
  777.         else
  778.         ll->y_list = alp;
  779.     }
  780.     }
  781.     ll->y_line = alp;
  782.     print_al("add ", alp);
  783.     return 0;
  784. }
  785.  
  786. /* ---------------- Filling loop utilities ---------------- */
  787.  
  788. /* Insert a newly active line in the X ordering. */
  789. private void
  790. insert_x_new(active_line * alp, ll_ptr ll)
  791. {
  792.     register active_line *next;
  793.     register active_line *prev = &ll->x_head;
  794.  
  795.     alp->x_current = alp->start.x;
  796.     while (INCR_EXPR(x_step),
  797.        (next = prev->next) != 0 && x_order(next, alp) < 0
  798.     )
  799.     prev = next;
  800.     alp->next = next;
  801.     alp->prev = prev;
  802.     if (next != 0)
  803.     next->prev = alp;
  804.     prev->next = alp;
  805. }
  806.  
  807. /* Handle a line segment that just ended.  Return true iff this was */
  808. /* the end of a line sequence. */
  809. private bool
  810. end_x_line(active_line * alp)
  811. {
  812.     const segment *pseg = alp->pseg;
  813.     /*
  814.      * The computation of next relies on the fact that
  815.      * all subpaths have been closed.  When we cycle
  816.      * around to the other end of a subpath, we must be
  817.      * sure not to process the start/end point twice.
  818.      */
  819.     const segment *next =
  820.     (alp->direction == dir_up ?
  821.      (                /* Upward line, go forward along path. */
  822.      pseg->type == s_line_close ?    /* end of subpath */
  823.      ((const line_close_segment *)pseg)->sub->next :
  824.      pseg->next) :
  825.      (                /* Downward line, go backward along path. */
  826.      pseg->type == s_start ?    /* start of subpath */
  827.      ((const subpath *)pseg)->last->prev :
  828.      pseg->prev)
  829.     );
  830.     gs_fixed_point npt;
  831.  
  832.     npt.y = next->pt.y;
  833.     if_debug5('F', "[F]ended 0x%lx: pseg=0x%lx y=%f next=0x%lx npt.y=%f\n",
  834.           (ulong) alp, (ulong) pseg, fixed2float(pseg->pt.y),
  835.           (ulong) next, fixed2float(npt.y));
  836.     if (npt.y <= pseg->pt.y) {    /* End of a line sequence */
  837.     active_line *nlp = alp->next;
  838.  
  839.     alp->prev->next = nlp;
  840.     if (nlp)
  841.         nlp->prev = alp->prev;
  842.     if_debug1('F', "[F]drop 0x%lx\n", (ulong) alp);
  843.     return true;
  844.     }
  845.     alp->pseg = next;
  846.     npt.x = next->pt.x;
  847.     set_al_points(alp, alp->end, npt);
  848.     print_al("repl", alp);
  849.     return false;
  850. }
  851.  
  852. #define loop_fill_rectangle(x, y, w, h)\
  853.   gx_fill_rectangle_device_rop(x, y, w, h, pdevc, dev, lop)
  854. #define loop_fill_rectangle_direct(x, y, w, h)\
  855.   (fill_direct ?\
  856.    (*fill_rect)(dev, x, y, w, h, cindex) :\
  857.    gx_fill_rectangle_device_rop(x, y, w, h, pdevc, dev, lop))
  858.  
  859. /* ---------------- Scan line filling loop ---------------- */
  860.  
  861. /* Forward references */
  862. private void set_scan_line_points(P2(active_line *, fixed));
  863.  
  864. /* Main filling loop. */
  865. private int
  866. fill_loop_by_scan_lines(ll_ptr ll, gx_device * dev,
  867.            const gx_fill_params * params, const gx_device_color * pdevc,
  868.              gs_logical_operation_t lop, const gs_fixed_rect * pbox,
  869.             fixed adjust_left, fixed adjust_right,
  870.             fixed adjust_below, fixed adjust_above, fixed band_mask)
  871. {
  872.     int rule = params->rule;
  873.     fixed fixed_flat = float2fixed(params->flatness);
  874.     bool fill_direct = color_writes_pure(pdevc, lop);
  875.     gx_color_index cindex;
  876.  
  877.     dev_proc_fill_rectangle((*fill_rect));
  878.     active_line *yll = ll->y_list;
  879.     fixed y_limit = pbox->q.y;
  880.     fixed y;
  881.  
  882.     /*
  883.      * The meaning of adjust_below (B) and adjust_above (A) is that
  884.      * the pixels that would normally be painted at coordinate Y get
  885.      * "smeared" to coordinates Y-B through Y+A-epsilon, inclusive.
  886.      * This is equivalent to saying that the pixels actually painted
  887.      * at coordinate Y are those contributed by scan lines Y-A+epsilon
  888.      * through Y+B, inclusive, or up to Y+B+epsilon, half-open.
  889.      * (A = B = 0 is a special case, equivalent to B = 0, A = epsilon.)
  890.      */
  891.     fixed look_below =
  892.     (adjust_above == fixed_0 ? fixed_0 : adjust_above - fixed_epsilon);
  893.     fixed look_above =
  894.     adjust_below + fixed_epsilon;
  895.     fixed look_height = look_above + look_below;
  896.     bool do_adjust = look_height > fixed_epsilon;
  897.  
  898.     if (yll == 0)        /* empty list */
  899.     return 0;
  900.     if (fill_direct)
  901.     cindex = pdevc->colors.pure,
  902.         fill_rect = dev_proc(dev, fill_rectangle);
  903. #define next_pixel_center(y)\
  904.   (fixed_pixround(y) + fixed_half)
  905.     y = next_pixel_center(yll->start.y) - look_below;    /* first Y sample point */
  906.     ll->x_list = 0;
  907.     ll->x_head.x_current = min_fixed;    /* stop backward scan */
  908.     while (1) {
  909.     active_line *alp, *nlp;
  910.     fixed x;
  911.     fixed ya = y + look_height;
  912.  
  913.     INCR(iter);
  914.     /* Move newly active lines from y to x list. */
  915.     while (yll != 0 && yll->start.y < ya) {
  916.         active_line *ynext = yll->next;    /* insert smashes next/prev links */
  917.  
  918.         if (yll->direction == dir_horizontal) {    /* Ignore for now. */
  919.         } else {
  920.         insert_x_new(yll, ll);
  921.         set_scan_line_points(yll, fixed_flat);
  922.         }
  923.         yll = ynext;
  924.     }
  925.     /* Check whether we've reached the maximum y. */
  926.     if (y >= y_limit)
  927.         break;
  928.     if (ll->x_list == 0) {    /* No active lines, skip to next start */
  929.         if (yll == 0)
  930.         break;        /* no lines left */
  931.         y = next_pixel_center(yll->start.y) - look_below;
  932.         continue;
  933.     }
  934.     /* Update active lines to y. */
  935.     x = min_fixed;
  936.     for (alp = ll->x_list; alp != 0; alp = nlp) {
  937.         fixed nx;
  938.  
  939.         nlp = alp->next;
  940.       e:if (alp->end.y <= y) {
  941.         if (end_x_line(alp))
  942.             continue;
  943.         set_scan_line_points(alp, fixed_flat);
  944.         goto e;
  945.         }
  946.         /* Note that if Y adjustment is in effect, */
  947.         /* alp->start.y might be greater than y. */
  948.         nx = alp->x_current =
  949.         (alp->start.y >= y ? alp->start.x :
  950.          alp->curve_k < 0 ?
  951.          al_x_at_y(alp, y) :
  952.          gx_curve_x_at_y(&alp->cursor, y));
  953.         if (nx < x) {    /* Move this line backward in the list. */
  954.         active_line *ilp = alp;
  955.  
  956.         while (nx < (ilp = ilp->prev)->x_current);
  957.         /* Now ilp->x_current <= nx < ilp->next->x_cur. */
  958.         alp->prev->next = alp->next;
  959.         if (alp->next)
  960.             alp->next->prev = alp->prev;
  961.         if (ilp->next)
  962.             ilp->next->prev = alp;
  963.         alp->next = ilp->next;
  964.         ilp->next = alp;
  965.         alp->prev = ilp;
  966.         continue;
  967.         }
  968.         x = nx;
  969.     }
  970.  
  971.     /* Fill inside regions at y. */
  972.     {
  973.         int inside = 0;
  974.         int x1_prev = min_int;
  975.  
  976.         /* rule = -1 for winding number rule, i.e. */
  977.         /* we are inside if the winding number is non-zero; */
  978.         /* rule = 1 for even-odd rule, i.e. */
  979.         /* we are inside if the winding number is odd. */
  980. #define inside_path_p() ((inside & rule) != 0)
  981.         INCR(band);
  982.         for (alp = ll->x_list; alp != 0; alp = alp->next) {        /* We're outside a filled region. */
  983.         int x0 = fixed2int_pixround(alp->x_current -
  984.                         adjust_left);
  985.  
  986.         /*
  987.          * This doesn't handle lines that cross
  988.          * within the adjustment region, but it's a
  989.          * good start.
  990.          */
  991.         if (do_adjust && alp->end.x < alp->start.x) {
  992.             fixed xa = (alp->end.y < ya ? alp->end.x :
  993.                 alp->curve_k < 0 ?
  994.                 al_x_at_y(alp, ya) :
  995.                 gx_curve_x_at_y(&alp->cursor,
  996.                         ya));
  997.             int x0a = fixed2int_pixround(xa -
  998.                          adjust_left);
  999.  
  1000.             if (x0a < x0)
  1001.             x0 = x0a;
  1002.         }
  1003.         for (;;) {    /* We're inside a filled region. */
  1004.             print_al("step", alp);
  1005.             INCR(band_step);
  1006.             inside += alp->direction;
  1007.             if (!inside_path_p())
  1008.             break;
  1009.             /*
  1010.              * Since we're dealing with closed paths, the test for
  1011.              * alp == 0 shouldn't be needed, but we may have omitted
  1012.              * lines that are to the right of the clipping region.
  1013.              */
  1014.             if ((alp = alp->next) == 0)
  1015.             goto out;
  1016.         }
  1017. #undef inside_path_p
  1018.         /*
  1019.          * We just went from inside to outside, so fill the region.
  1020.          * Avoid writing pixels twice.
  1021.          */
  1022.         if (x0 < x1_prev)
  1023.             x0 = x1_prev;
  1024.         {
  1025.             int x1 = fixed2int_rounded(alp->x_current +
  1026.                            adjust_right);
  1027.  
  1028.             if (do_adjust && alp->end.x > alp->start.x) {
  1029.             fixed xa = (alp->end.y < ya ?
  1030.                     alp->end.x :
  1031.                     alp->curve_k < 0 ?
  1032.                     al_x_at_y(alp, ya) :
  1033.                     gx_curve_x_at_y(&alp->cursor,
  1034.                             ya));
  1035.             int x1a = fixed2int_rounded(xa +
  1036.                             adjust_right);
  1037.  
  1038.             if (x1a > x1)
  1039.                 x1 = x1a;
  1040.             }
  1041.             if (x1 > x0) {
  1042.             int code =
  1043.             loop_fill_rectangle_direct(x0,
  1044.                            fixed2int_var(y),
  1045.                            x1 - x0, 1);
  1046.  
  1047.             if_debug3('F', "[F]drawing [%d:%d),%d\n",
  1048.                   x0, x1, fixed2int_var(y));
  1049.             if (code < 0)
  1050.                 return code;
  1051.             x1_prev = x1;
  1052.             }
  1053.         }
  1054.         }
  1055.       out:;
  1056.     }
  1057.     y += fixed_1;
  1058.     }
  1059.     return 0;
  1060. }
  1061.  
  1062. private void
  1063. set_scan_line_points(active_line * alp, fixed fixed_flat)
  1064. {
  1065.     const segment *pseg = alp->pseg;
  1066.     const gs_fixed_point *pp0;
  1067.  
  1068.     if (alp->direction < 0) {
  1069.     pseg =
  1070.         (pseg->type == s_line_close ?
  1071.          ((const line_close_segment *)pseg)->sub->next :
  1072.          pseg->next);
  1073.     if (pseg->type != s_curve) {
  1074.         alp->curve_k = -1;
  1075.         return;
  1076.     }
  1077.     pp0 = &alp->end;
  1078.     } else {
  1079.     if (pseg->type != s_curve) {
  1080.         alp->curve_k = -1;
  1081.         return;
  1082.     }
  1083.     pp0 = &alp->start;
  1084.     }
  1085. #define pcseg ((const curve_segment *)pseg)
  1086.     alp->curve_k =
  1087.     gx_curve_log2_samples(pp0->x, pp0->y, pcseg, fixed_flat);
  1088.     gx_curve_cursor_init(&alp->cursor, pp0->x, pp0->y, pcseg,
  1089.              alp->curve_k);
  1090. #undef pcseg
  1091. }
  1092.  
  1093. /* ---------------- Trapezoid filling loop ---------------- */
  1094.  
  1095. /* Forward references */
  1096. private int fill_slant_adjust(P12(fixed, fixed, fixed, fixed, fixed,
  1097.                   fixed, fixed, fixed, const gs_fixed_rect *,
  1098.          const gx_device_color *, gx_device *, gs_logical_operation_t));
  1099. private void resort_x_line(P1(active_line *));
  1100.  
  1101. /****** PATCH ******/
  1102. #define loop_fill_trapezoid_fixed(fx0, fw0, fy0, fx1, fw1, fh)\
  1103.   loop_fill_trap(dev, fx0, fw0, fy0, fx1, fw1, fh, pbox, pdevc, lop)
  1104. private int
  1105. loop_fill_trap(gx_device * dev, fixed fx0, fixed fw0, fixed fy0,
  1106.            fixed fx1, fixed fw1, fixed fh, const gs_fixed_rect * pbox,
  1107.            const gx_device_color * pdevc, gs_logical_operation_t lop)
  1108. {
  1109.     fixed fy1 = fy0 + fh;
  1110.     fixed ybot = max(fy0, pbox->p.y);
  1111.     fixed ytop = min(fy1, pbox->q.y);
  1112.     gs_fixed_edge left, right;
  1113.  
  1114.     if (ybot >= ytop)
  1115.     return 0;
  1116.     left.start.y = right.start.y = fy0;
  1117.     left.end.y = right.end.y = fy1;
  1118.     right.start.x = (left.start.x = fx0) + fw0;
  1119.     right.end.x = (left.end.x = fx1) + fw1;
  1120.     return (*dev_proc(dev, fill_trapezoid))
  1121.     (dev, &left, &right, ybot, ytop, false, pdevc, lop);
  1122. }
  1123. /****** END PATCH ******/
  1124.  
  1125. /* Main filling loop.  Takes lines off of y_list and adds them to */
  1126. /* x_list as needed.  band_mask limits the size of each band, */
  1127. /* by requiring that ((y1 - 1) & band_mask) == (y0 & band_mask). */
  1128. private int
  1129. fill_loop_by_trapezoids(ll_ptr ll, gx_device * dev,
  1130.            const gx_fill_params * params, const gx_device_color * pdevc,
  1131.              gs_logical_operation_t lop, const gs_fixed_rect * pbox,
  1132.             fixed adjust_left, fixed adjust_right,
  1133.             fixed adjust_below, fixed adjust_above, fixed band_mask)
  1134. {
  1135.     int rule = params->rule;
  1136.     const fixed y_limit = pbox->q.y;
  1137.     active_line *yll = ll->y_list;
  1138.     fixed y;
  1139.     int code;
  1140.     bool fill_direct = color_writes_pure(pdevc, lop);
  1141.     gx_color_index cindex;
  1142.  
  1143.     dev_proc_fill_rectangle((*fill_rect));
  1144. /*
  1145.  * Define a faster test for
  1146.  *      fixed2int_pixround(y - below) != fixed2int_pixround(y + above)
  1147.  * where we know
  1148.  *      0 <= below <= _fixed_pixround_v,
  1149.  *      0 <= above <= min(fixed_half, fixed_1 - below).
  1150.  * Subtracting out the integer parts, this is equivalent to
  1151.  *      fixed2int_pixround(fixed_fraction(y) - below) !=
  1152.  *        fixed2int_pixround(fixed_fraction(y) + above)
  1153.  * or to
  1154.  *      fixed2int(fixed_fraction(y) + _fixed_pixround_v - below) !=
  1155.  *        fixed2int(fixed_fraction(y) + _fixed_pixround_v + above)
  1156.  * Letting A = _fixed_pixround_v - below and B = _fixed_pixround_v + above,
  1157.  * we can rewrite this as
  1158.  *      fixed2int(fixed_fraction(y) + A) != fixed2int(fixed_fraction(y) + B)
  1159.  * Because of the range constraints given above, this is true precisely when
  1160.  *      fixed_fraction(y) + A < fixed_1 && fixed_fraction(y) + B >= fixed_1
  1161.  * or equivalently
  1162.  *      fixed_fraction(y + B) < B - A.
  1163.  * i.e.
  1164.  *      fixed_fraction(y + _fixed_pixround_v + above) < below + above
  1165.  */
  1166.     fixed y_span_delta = _fixed_pixround_v + adjust_above;
  1167.     fixed y_span_limit = adjust_below + adjust_above;
  1168.  
  1169. #define adjusted_y_spans_pixel(y)\
  1170.   fixed_fraction((y) + y_span_delta) < y_span_limit
  1171.  
  1172.     if (yll == 0)
  1173.     return 0;        /* empty list */
  1174.     if (fill_direct)
  1175.     cindex = pdevc->colors.pure,
  1176.         fill_rect = dev_proc(dev, fill_rectangle);
  1177.     y = yll->start.y;        /* first Y value */
  1178.     ll->x_list = 0;
  1179.     ll->x_head.x_current = min_fixed;    /* stop backward scan */
  1180.     while (1) {
  1181.     fixed y1;
  1182.     active_line *endp, *alp, *stopx;
  1183.     fixed x;
  1184.     int draw;
  1185.  
  1186.     INCR(iter);
  1187.     /* Move newly active lines from y to x list. */
  1188.     while (yll != 0 && yll->start.y == y) {
  1189.         active_line *ynext = yll->next;    /* insert smashes next/prev links */
  1190.  
  1191.         if (yll->direction == dir_horizontal) {    /* This is a hack to make sure that */
  1192.         /* isolated horizontal lines get stroked. */
  1193.         int yi = fixed2int_pixround(y - adjust_below);
  1194.         int xi, wi;
  1195.  
  1196.         if (yll->start.x <= yll->end.x)
  1197.             xi = fixed2int_pixround(yll->start.x -
  1198.                         adjust_left),
  1199.             wi = fixed2int_pixround(yll->end.x +
  1200.                         adjust_right) - xi;
  1201.         else
  1202.             xi = fixed2int_pixround(yll->end.x -
  1203.                         adjust_left),
  1204.             wi = fixed2int_pixround(yll->start.x +
  1205.                         adjust_right) - xi;
  1206.         code = loop_fill_rectangle_direct(xi, yi, wi, 1);
  1207.         if (code < 0)
  1208.             return code;
  1209.         } else
  1210.         insert_x_new(yll, ll);
  1211.         yll = ynext;
  1212.     }
  1213.     /* Check whether we've reached the maximum y. */
  1214.     if (y >= y_limit)
  1215.         break;
  1216.     if (ll->x_list == 0) {    /* No active lines, skip to next start */
  1217.         if (yll == 0)
  1218.         break;        /* no lines left */
  1219.         y = yll->start.y;
  1220.         continue;
  1221.     }
  1222.     /* Find the next evaluation point. */
  1223.     /* Start by finding the smallest y value */
  1224.     /* at which any currently active line ends */
  1225.     /* (or the next to-be-active line begins). */
  1226.     y1 = (yll != 0 ? yll->start.y : y_limit);
  1227.     /* Make sure we don't exceed the maximum band height. */
  1228.     {
  1229.         fixed y_band = y | ~band_mask;
  1230.  
  1231.         if (y1 > y_band)
  1232.         y1 = y_band + 1;
  1233.     }
  1234.     for (alp = ll->x_list; alp != 0; alp = alp->next)
  1235.         if (alp->end.y < y1)
  1236.         y1 = alp->end.y;
  1237. #ifdef DEBUG
  1238.     if (gs_debug_c('F')) {
  1239.         dlprintf2("[F]before loop: y=%f y1=%f:\n",
  1240.               fixed2float(y), fixed2float(y1));
  1241.         print_line_list(ll->x_list);
  1242.     }
  1243. #endif
  1244.     /* Now look for line intersections before y1. */
  1245.     x = min_fixed;
  1246. #define have_pixels()\
  1247.   (fixed_pixround(y - adjust_below) < fixed_pixround(y1 + adjust_above))
  1248.     draw = (have_pixels()? 1 : -1);
  1249.     /*
  1250.      * Loop invariants:
  1251.      *      alp = endp->next;
  1252.      *      for all lines lp from stopx up to alp,
  1253.      *        lp->x_next = al_x_at_y(lp, y1).
  1254.      */
  1255.     for (alp = stopx = ll->x_list;
  1256.          INCR_EXPR(find_y), alp != 0;
  1257.          endp = alp, alp = alp->next
  1258.         ) {
  1259.         fixed nx = al_x_at_y(alp, y1);
  1260.         fixed dx_old, dx_den;
  1261.  
  1262.         /* Check for intersecting lines. */
  1263.         if (nx >= x)
  1264.         x = nx;
  1265.         else if
  1266.             (draw >= 0 &&    /* don't bother if no pixels */
  1267.              (dx_old = alp->x_current - endp->x_current) >= 0 &&
  1268.              (dx_den = dx_old + endp->x_next - nx) > dx_old
  1269.         ) {        /* Make a good guess at the intersection */
  1270.         /* Y value using only local information. */
  1271.         fixed dy = y1 - y, y_new;
  1272.  
  1273.         if_debug3('F', "[F]cross: dy=%g, dx_old=%g, dx_new=%g\n",
  1274.               fixed2float(dy), fixed2float(dx_old),
  1275.               fixed2float(dx_den - dx_old));
  1276.         /* Do the computation in single precision */
  1277.         /* if the values are small enough. */
  1278.         y_new =
  1279.             ((dy | dx_old) < 1L << (size_of(fixed) * 4 - 1) ?
  1280.              dy * dx_old / dx_den :
  1281.              (INCR_EXPR(mq_cross), fixed_mult_quo(dy, dx_old, dx_den)))
  1282.             + y;
  1283.         /* The crossing value doesn't have to be */
  1284.         /* very accurate, but it does have to be */
  1285.         /* greater than y and less than y1. */
  1286.         if_debug3('F', "[F]cross y=%g, y_new=%g, y1=%g\n",
  1287.               fixed2float(y), fixed2float(y_new),
  1288.               fixed2float(y1));
  1289.         stopx = alp;
  1290.         if (y_new <= y) {
  1291.             /*
  1292.              * This isn't possible.  Recompute the intersection
  1293.              * accurately.
  1294.              */
  1295.             fixed ys, xs0, xs1, ye, xe0, xe1, dy, dx0, dx1;
  1296.  
  1297.             INCR(cross_slow);
  1298.             if (endp->start.y < alp->start.y)
  1299.             ys = alp->start.y,
  1300.                 xs0 = al_x_at_y(endp, ys), xs1 = alp->start.x;
  1301.             else
  1302.             ys = endp->start.y,
  1303.                 xs0 = endp->start.x, xs1 = al_x_at_y(alp, ys);
  1304.             if (endp->end.y > alp->end.y)
  1305.             ye = alp->end.y,
  1306.                 xe0 = al_x_at_y(endp, ye), xe1 = alp->end.x;
  1307.             else
  1308.             ye = endp->end.y,
  1309.                 xe0 = endp->end.x, xe1 = al_x_at_y(alp, ye);
  1310.             dy = ye - ys;
  1311.             dx0 = xe0 - xs0;
  1312.             dx1 = xe1 - xs1;
  1313.             /* We need xs0 + cross * dx0 == xs1 + cross * dx1. */
  1314.             if (dx0 == dx1) {
  1315.             /* The two lines are coincident.  Do nothing. */
  1316.             y_new = y1;
  1317.             } else {
  1318.             double cross = (double)(xs0 - xs1) / (dx1 - dx0);
  1319.  
  1320.             y_new = (fixed)(ys + cross * dy);
  1321.             if (y_new <= y) {
  1322.                 /*
  1323.                  * This can only happen through some kind of
  1324.                  * numeric disaster, but we have to check.
  1325.                  */
  1326.                 INCR(cross_low);
  1327.                 y_new = y + fixed_epsilon;
  1328.             }
  1329.             }
  1330.         }
  1331.         if (y_new < y1) {
  1332.             y1 = y_new;
  1333.             nx = al_x_at_y(alp, y1);
  1334.             draw = 0;
  1335.         }
  1336.         if (nx > x)
  1337.             x = nx;
  1338.         }
  1339.         alp->x_next = nx;
  1340.     }
  1341.     /* Recompute next_x for lines before the intersection. */
  1342.     for (alp = ll->x_list; alp != stopx; alp = alp->next)
  1343.         alp->x_next = al_x_at_y(alp, y1);
  1344. #ifdef DEBUG
  1345.     if (gs_debug_c('F')) {
  1346.         dlprintf1("[F]after loop: y1=%f\n", fixed2float(y1));
  1347.         print_line_list(ll->x_list);
  1348.     }
  1349. #endif
  1350.     /* Fill a multi-trapezoid band for the active lines. */
  1351.     /* Don't bother if no pixel centers lie within the band. */
  1352.     if (draw > 0 || (draw == 0 && have_pixels())) {
  1353.  
  1354. /*******************************************************************/
  1355. /* For readability, we start indenting from the left margin again. */
  1356. /*******************************************************************/
  1357.  
  1358.         fixed height = y1 - y;
  1359.         fixed xlbot, xltop;    /* as of last "outside" line */
  1360.         int inside = 0;
  1361.         active_line *nlp;
  1362.  
  1363.         INCR(band);
  1364.         for (x = min_fixed, alp = ll->x_list; alp != 0; alp = nlp) {
  1365.         fixed xbot = alp->x_current;
  1366.         fixed xtop = alp->x_current = alp->x_next;
  1367.  
  1368. #define nx xtop
  1369.         fixed wtop;
  1370.         int xi, xli;
  1371.         int code;
  1372.  
  1373.         print_al("step", alp);
  1374.         INCR(band_step);
  1375.         nlp = alp->next;
  1376.         /* Handle ended or out-of-order lines.  After this, */
  1377.         /* the only member of alp we use is alp->direction. */
  1378.         if (alp->end.y != y1 || !end_x_line(alp)) {
  1379.             if (nx <= x)
  1380.             resort_x_line(alp);
  1381.             else
  1382.             x = nx;
  1383.         }
  1384. #undef nx
  1385.         /* rule = -1 for winding number rule, i.e. */
  1386.         /* we are inside if the winding number is non-zero; */
  1387.         /* rule = 1 for even-odd rule, i.e. */
  1388.         /* we are inside if the winding number is odd. */
  1389. #define inside_path_p() ((inside & rule) != 0)
  1390.         if (!inside_path_p()) {        /* i.e., outside */
  1391.             inside += alp->direction;
  1392.             if (inside_path_p())    /* about to go in */
  1393.             xlbot = xbot, xltop = xtop;
  1394.             continue;
  1395.         }
  1396.         /* We're inside a region being filled. */
  1397.         inside += alp->direction;
  1398.         if (inside_path_p())    /* not about to go out */
  1399.             continue;
  1400. #undef inside_path_p
  1401.         /* We just went from inside to outside, so fill the region. */
  1402.         wtop = xtop - xltop;
  1403.         INCR(band_fill);
  1404.         /*
  1405.          * If lines are temporarily out of order, we might have
  1406.          * xtop < xltop.  Patch this up now if necessary.  Note that
  1407.          * we can't test wtop < 0, because the subtraction might
  1408.          * overflow.
  1409.          */
  1410.         if (xtop < xltop) {
  1411.             if_debug2('f', "[f]patch %g,%g\n",
  1412.                   fixed2float(xltop), fixed2float(xtop));
  1413.             xtop = xltop += arith_rshift(wtop, 1);
  1414.             wtop = 0;
  1415.         }
  1416.         if ((adjust_left | adjust_right) != 0) {
  1417.             xlbot -= adjust_left;
  1418.             xbot += adjust_right;
  1419.             xltop -= adjust_left;
  1420.             xtop += adjust_right;
  1421.             wtop = xtop - xltop;
  1422.         }
  1423.         if ((xli = fixed2int_var_pixround(xltop)) ==
  1424.             fixed2int_var_pixround(xlbot) &&
  1425.             (xi = fixed2int_var_pixround(xtop)) ==
  1426.             fixed2int_var_pixround(xbot)
  1427.             ) {        /* Rectangle. */
  1428.             int yi = fixed2int_pixround(y - adjust_below);
  1429.             int wi = fixed2int_pixround(y1 + adjust_above) - yi;
  1430.  
  1431.             code = loop_fill_rectangle_direct(xli, yi,
  1432.                               xi - xli, wi);
  1433.         } else if ((adjust_below | adjust_above) != 0) {
  1434.             /*
  1435.              * We want to get the effect of filling an area whose
  1436.              * outline is formed by dragging a square of side adj2
  1437.              * along the border of the trapezoid.  This is *not*
  1438.              * equivalent to simply expanding the corners by
  1439.              * adjust: There are 3 cases needing different
  1440.              * algorithms, plus rectangles as a fast special case.
  1441.              */
  1442.             fixed wbot = xbot - xlbot;
  1443.  
  1444.             if (xltop <= xlbot) {
  1445.             if (xtop >= xbot) {    /* Top wider than bottom. */
  1446.                 code = loop_fill_trapezoid_fixed(
  1447.                           xlbot, wbot, y - adjust_below,
  1448.                                xltop, wtop, height);
  1449.                 if (adjusted_y_spans_pixel(y1)) {
  1450.                 if (code < 0)
  1451.                     return code;
  1452.                 INCR(afill);
  1453.                 code = loop_fill_rectangle_direct(
  1454.                  xli, fixed2int_pixround(y1 - adjust_below),
  1455.                      fixed2int_var_pixround(xtop) - xli, 1);
  1456.                 }
  1457.             } else {    /* Slanted trapezoid. */
  1458.                 code = fill_slant_adjust(xlbot, xbot, y,
  1459.                       xltop, xtop, height, adjust_below,
  1460.                              adjust_above, pbox,
  1461.                              pdevc, dev, lop);
  1462.             }
  1463.             } else {
  1464.             if (xtop <= xbot) {    /* Bottom wider than top. */
  1465.                 if (adjusted_y_spans_pixel(y)) {
  1466.                 INCR(afill);
  1467.                 xli = fixed2int_var_pixround(xlbot);
  1468.                 code = loop_fill_rectangle_direct(
  1469.                   xli, fixed2int_pixround(y - adjust_below),
  1470.                      fixed2int_var_pixround(xbot) - xli, 1);
  1471.                 if (code < 0)
  1472.                     return code;
  1473.                 }
  1474.                 code = loop_fill_trapezoid_fixed(
  1475.                           xlbot, wbot, y + adjust_above,
  1476.                                xltop, wtop, height);
  1477.             } else {    /* Slanted trapezoid. */
  1478.                 code = fill_slant_adjust(xlbot, xbot, y,
  1479.                       xltop, xtop, height, adjust_below,
  1480.                              adjust_above, pbox,
  1481.                              pdevc, dev, lop);
  1482.             }
  1483.             }
  1484.         } else        /* No Y adjustment. */
  1485.             code = loop_fill_trapezoid_fixed(xlbot, xbot - xlbot,
  1486.                              y, xltop, wtop, height);
  1487.         if (code < 0)
  1488.             return code;
  1489.         }
  1490.  
  1491. /**************************************************************/
  1492. /* End of section requiring less indentation for readability. */
  1493. /**************************************************************/
  1494.  
  1495.     } else {        /* Just scan for ended or out-of-order lines. */
  1496.         active_line *nlp;
  1497.  
  1498.         for (x = min_fixed, alp = ll->x_list; alp != 0;
  1499.          alp = nlp
  1500.         ) {
  1501.         fixed nx = alp->x_current = alp->x_next;
  1502.  
  1503.         nlp = alp->next;
  1504.         if_debug4('F',
  1505.               "[F]check 0x%lx,x=%g 0x%lx,x=%g\n",
  1506.               (ulong) alp->prev, fixed2float(x),
  1507.               (ulong) alp, fixed2float(nx));
  1508.         if (alp->end.y == y1) {
  1509.             if (end_x_line(alp))
  1510.             continue;
  1511.         }
  1512.         if (nx <= x)
  1513.             resort_x_line(alp);
  1514.         else
  1515.             x = nx;
  1516.         }
  1517.     }
  1518. #ifdef DEBUG
  1519.     if (gs_debug_c('f')) {
  1520.         int code = check_line_list(ll->x_list);
  1521.  
  1522.         if (code < 0)
  1523.         return code;
  1524.     }
  1525. #endif
  1526.     y = y1;
  1527.     }
  1528.     return 0;
  1529. }
  1530.  
  1531. /*
  1532.  * Handle the case of a slanted trapezoid with adjustment.
  1533.  * To do this exactly right requires filling a central trapezoid
  1534.  * (or rectangle) plus two horizontal almost-rectangles.
  1535.  */
  1536. private int
  1537. fill_slant_adjust(fixed xlbot, fixed xbot, fixed y,
  1538.           fixed xltop, fixed xtop, fixed height, fixed adjust_below,
  1539.           fixed adjust_above, const gs_fixed_rect * pbox,
  1540.           const gx_device_color * pdevc, gx_device * dev,
  1541.           gs_logical_operation_t lop)
  1542. {
  1543.     fixed y1 = y + height;
  1544.  
  1545.     dev_proc_fill_trapezoid((*fill_trap)) =
  1546.     dev_proc(dev, fill_trapezoid);
  1547.     const fixed yb = y - adjust_below;
  1548.     const fixed ya = y + adjust_above;
  1549.     const fixed y1b = y1 - adjust_below;
  1550.     const fixed y1a = y1 + adjust_above;
  1551.     const gs_fixed_edge *plbot;
  1552.     const gs_fixed_edge *prbot;
  1553.     const gs_fixed_edge *pltop;
  1554.     const gs_fixed_edge *prtop;
  1555.     gs_fixed_edge vert_left, slant_left, vert_right, slant_right;
  1556.     int code;
  1557.  
  1558.     INCR(slant);
  1559.  
  1560.     /* Set up all the edges, even though we may not need them all. */
  1561.  
  1562.     if (xlbot < xltop) {    /* && xbot < xtop */
  1563.     vert_left.start.x = vert_left.end.x = xlbot;
  1564.     vert_left.start.y = yb, vert_left.end.y = ya;
  1565.     vert_right.start.x = vert_right.end.x = xtop;
  1566.     vert_right.start.y = y1b, vert_right.end.y = y1a;
  1567.     slant_left.start.y = ya, slant_left.end.y = y1a;
  1568.     slant_right.start.y = yb, slant_right.end.y = y1b;
  1569.     plbot = &vert_left, prbot = &slant_right,
  1570.         pltop = &slant_left, prtop = &vert_right;
  1571.     } else {
  1572.     vert_left.start.x = vert_left.end.x = xltop;
  1573.     vert_left.start.y = y1b, vert_left.end.y = y1a;
  1574.     vert_right.start.x = vert_right.end.x = xbot;
  1575.     vert_right.start.y = yb, vert_right.end.y = ya;
  1576.     slant_left.start.y = yb, slant_left.end.y = y1b;
  1577.     slant_right.start.y = ya, slant_right.end.y = y1a;
  1578.     plbot = &slant_left, prbot = &vert_right,
  1579.         pltop = &vert_left, prtop = &slant_right;
  1580.     }
  1581.     slant_left.start.x = xlbot, slant_left.end.x = xltop;
  1582.     slant_right.start.x = xbot, slant_right.end.x = xtop;
  1583.  
  1584.     if (ya >= y1b) {
  1585.     /*
  1586.      * The upper and lower adjustment bands overlap.
  1587.      * Since the entire entity is less than 2 pixels high
  1588.      * in this case, we could handle it very efficiently
  1589.      * with no more than 2 rectangle fills, but for right now
  1590.      * we don't attempt to do this.
  1591.      */
  1592.     int iyb = fixed2int_var_pixround(yb);
  1593.     int iya = fixed2int_var_pixround(ya);
  1594.     int iy1b = fixed2int_var_pixround(y1b);
  1595.     int iy1a = fixed2int_var_pixround(y1a);
  1596.  
  1597.     INCR(slant_shallow);
  1598.     if (iy1b > iyb) {
  1599.         code = (*fill_trap) (dev, plbot, prbot,
  1600.                  yb, y1b, false, pdevc, lop);
  1601.         if (code < 0)
  1602.         return code;
  1603.     }
  1604.     if (iya > iy1b) {
  1605.         int ix = fixed2int_var_pixround(vert_left.start.x);
  1606.         int iw = fixed2int_var_pixround(vert_right.start.x) - ix;
  1607.  
  1608.         code = loop_fill_rectangle(ix, iy1b, iw, iya - iy1b);
  1609.         if (code < 0)
  1610.         return code;
  1611.     }
  1612.     if (iy1a > iya)
  1613.         code = (*fill_trap) (dev, pltop, prtop,
  1614.                  ya, y1a, false, pdevc, lop);
  1615.     else
  1616.         code = 0;
  1617.     } else {
  1618.     /*
  1619.      * Clip the trapezoid if possible.  This can save a lot
  1620.      * of work when filling paths that cross band boundaries.
  1621.      */
  1622.     fixed yac;
  1623.  
  1624.     if (pbox->p.y < ya) {
  1625.         code = (*fill_trap) (dev, plbot, prbot,
  1626.                  yb, ya, false, pdevc, lop);
  1627.         if (code < 0)
  1628.         return code;
  1629.         yac = ya;
  1630.     } else
  1631.         yac = pbox->p.y;
  1632.     if (pbox->q.y > y1b) {
  1633.         code = (*fill_trap) (dev, &slant_left, &slant_right,
  1634.                  yac, y1b, false, pdevc, lop);
  1635.         if (code < 0)
  1636.         return code;
  1637.         code = (*fill_trap) (dev, pltop, prtop,
  1638.                  y1b, y1a, false, pdevc, lop);
  1639.     } else
  1640.         code = (*fill_trap) (dev, &slant_left, &slant_right,
  1641.                  yac, pbox->q.y, false, pdevc, lop);
  1642.     }
  1643.     return code;
  1644. }
  1645.  
  1646. /* Re-sort the x list by moving alp backward to its proper spot. */
  1647. private void
  1648. resort_x_line(active_line * alp)
  1649. {
  1650.     active_line *prev = alp->prev;
  1651.     active_line *next = alp->next;
  1652.  
  1653.     prev->next = next;
  1654.     if (next)
  1655.     next->prev = prev;
  1656.     while (x_order(prev, alp) > 0) {
  1657.     if_debug2('F', "[F]swap 0x%lx,0x%lx\n",
  1658.           (ulong) alp, (ulong) prev);
  1659.     next = prev, prev = prev->prev;
  1660.     }
  1661.     alp->next = next;
  1662.     alp->prev = prev;
  1663.     /* next might be null, if alp was in */
  1664.     /* the correct spot already. */
  1665.     if (next)
  1666.     next->prev = alp;
  1667.     prev->next = alp;
  1668. }
  1669.